class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
      int len = prices.size();
      if(len == 0||len == 1) return 0;
      int cnt = 2 * k;
      vector<vector<int> >dp(len,vector<int>(cnt+1,0));
      for(int i = 0;i < cnt;i++){
        if(i % 2 == 1) dp[0][i] = -prices[0];
      }
      for(int i = 1;i < len;i++){
        dp[i][0] = dp[i-1][0];
        for(int j = 1;j <= cnt;j++){
          if(j % 2 == 1) {
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
          }else{
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
          }
        }
      }
      return dp[len-1][cnt];
    }
};
